// 17. 电话号码的字母组合
// https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
// 中等,给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
// 示例 1：
// 输入：digits = "23"
// 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
// 示例 2：
// 输入：digits = ""
// 输出：[]
// 示例 3：
// 输入：digits = "2"
// 输出：["a","b","c"]

#include <bits/stdc++.h>
using namespace std;

class Solution_1 {
    map<int,string> mapLetter = {{1,""},{2,"abc"},{3,"def"},{4,"ghi"},{5,"jkl"},{6,"mno"},{7,"pqrs"},{8,"tuv"},{9,"wxyz"},};
public:
    vector<string> letterCombinations(string digits) {
        queue<string> qu;
        for (auto c : mapLetter[digits[0]-'0']) {
            qu.push(string() + c);
        }
        for (size_t i=1; i<digits.size(); i++) {
            int size = qu.size();
            for (int j=0; j<size; j++) {
                string tmp = qu.front(); qu.pop();
                for (auto c : mapLetter[digits[i]-'0']) {
                    qu.push(tmp + c);
                }
            }
        }
        vector<string> ans;
        while(!qu.empty()) {
            ans.push_back(qu.front()); qu.pop();
        }
        return ans;
    }
};

class Solution_dfs {
    map<int,string> mapLetter = {{1,""},{2,"abc"},{3,"def"},{4,"ghi"},{5,"jkl"},{6,"mno"},{7,"pqrs"},{8,"tuv"},{9,"wxyz"},};
    vector<string> ans;
    void dfs(const string& digits, size_t index, string tmp) {
        if (index == digits.length()){
            ans.push_back(tmp);
            return ;
        }
        for (auto c : mapLetter[digits[index]-'0']) {
            tmp += c;
            dfs(digits, index+1, tmp);
            tmp.erase(tmp.size()-1);
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        if (!digits.empty()) {
            string tmp;
            dfs(digits, 0, tmp);
        }
        return ans;
    }
};
